package string.compare;

/**
 * @Classname : LongestPalindrome
 * @Description : 409. 最长回文串
 * https://leetcode.cn/problems/longest-palindrome/
 * @Author : chentianyu
 * @Date 2022/12/18 22:39
 */


public class LongestPalindrome {

    public int longestPalindrome(String s) {
        // 统计字母出现频数
        int[] table = new int[64];
        for (char c : s.toCharArray()) {
            table[c - 64]++;
        }
        // 累加出现频数为2的倍数的字母的个数
        int ans = 0;
        for (int i = 'A'; i <= 'z'; i++) {
            int n = table[i - 64];
            ans += (n % 2 == 0 ? n : n - 1);
        }
        // 若长度不一致，肯定是小于字符串长度，说明存在落单字母，可取1个置于中间构造最长回文串
        return ans == s.length() ? ans : ans + 1;
    }
}
